It will be helpful in understanding the invention to refer to the background of digital communications networks, which in recent years have been expanded to link virtually boundless numbers of data processors or computers of different designs in different geographic locations, and owned or administered by different entities. FIG. 1 depicts an exemplary network, wherein the circular "nodes" (11, 12, 13, etc.) include processor sites, and the lines connecting them (111, 112, 121, etc.) are physical transmission media or "circuits" by which the nodes communicate, by wire, by microwave (wireless), optically, or otherwise, including combinations of media. It is to be understood that this diagram is in "connection space"; that is, it depicts data connection relationships and not geographic relationships. For example, nodes 13 and 14 may be in the same room, while node 15 may be miles or thousands of miles away.
To establish standards for, and thereby facilitate communications between, nodes of different processor design and application, the International Organization for Standardization ("ISO") has set forth its "Open Systems Interconnection" ("OSI") Reference Model (ISO 7498), which defines seven functional levels or "layers" of communication in nodes communicating under OSI.
FIG. 2 depicts the layers and data flow in the OSI Reference Model for a hypothetical network segment. The Physical Layer 207 includes the functions necessary for transmission and reception of data on the transmission or physical medium 208, involving, for example, the conversion of digital data signals to and from the signal format used in the medium 208. The Data Link Layer 206 includes functions for facilitating communications between directly connected nodes in a network; these functions are not of particular interest here. The Network Layer 205, to which the present invention primarily relates, routes user data between nodes in the network. A "router" 209 comprises the functions of layers 205 through 207, to the extent the functions of such layers are implemented. A physical implementation of a router may perform only those functions, as depicted in node 23, or may be the portion (e.g., routers 211, 221 and 241) of a "full service" processor (e.g., nodes 21, 22, and 24) which performs the router functions, among other functions.
With further reference to FIG. 2, the Transport Layer 204 provides end-to-end services between communicating nodes, such as requesting confirmation of receipt of transmissions, transmissions of such confirmations, and retransmissions if no such confirmations are received. The higher levels, i.e., the Session, Presentation, and Application Layers (203, 202 and 201, respectively) support standardized application protocols which are not the subject of this disclosure.
Data stream 20 in FIG. 2 is exemplary of how information is transferred in the OSI Reference Model, in this case, from a user at node 21 to a user at node 24, by way of intermediate nodes 22 and 23. Routing decisions in the nodes are made at the Network Layer 205 in general accordance with routing strategies known in the art such as "shortest path," "best efforts," "least expensive" and the like, programmed or hard-wired into processors or circuits associated with the Network Layer 205. The routing decisions generally require an identification of the destination (intermediate or ultimate) for information received on physical medium 208 (corresponding to a "circuit"), an identification which may be carried along in the data stream. Other information may also be used (which may also be carried in the data stream), such as quality of service requested, which may determine which of alternative forwarding paths to use.
Network data communications, in contrast to voice communications, often are made in a "connectionless" mode. In that mode, "data packets" or "datagrams" of contiguous signals led by identifying "header" signals (and possibly terminated with identifying "trailer" signals) are routed from node to node between end users (e.g., node 21 to node 22 to node 23 to node 24 in FIG. 2) without "connection" in the sense of dedication of the entire end-to-end transmission path at any instant to the transmission. There is no connection at the Network Layer 205, and router 221, for example, having made a decision to forward a datagram to node 23, never "knows" (or "cares") if that datagram reaches nodes 23 or 24.
In OSI connectionless network service, a "virtual connection" 34--34 is nonetheless made at the Transport Layer 204. This is a connection in the sense that while there is no physical connection at any one time, communication is established between nodes 21 and 24 at Transport Layer 204 and above without reference to how data is communicated at the Network Layer 205 and below. That is, insofar as the layers 204 and up are concerned, there is a direct connection between nodes 21 and 24. The connection 34-34 is made at the Transport Layer 204 in OSI connectionless mode service when a datagram carrying a request for connection reaches node 24, that datagram is interpreted at the Transport Layer of node 24 as a request for connection, node 24 responds with a datagram confirming connection sent to node 21, and the Transport Layer of node 21 recognizes the confirmation.
To allow standardization at each layer, OSI defines protocols for or structures of data recognized at the respective layers. These structures are known as Protocol Data Units ("PDUs"). FIG. 3 depicts general PDU data structures for each layer. As suggested in FIG. 3, the PDUs are "nested" in the sense that each PDU includes the "client" PDU for the next higher or "client" layer, along with a "service header." A service header provides "protocol control information" relevant to its particular layer. For example, the "Network Service Header" 305 may include destination and quality of service information for Network Layer (routing) decisions.
Referring to FIGS. 2 and 3 in conjunction, user information to be communicated starts as an application data unit 31 and is prepared for transmission on the physical medium 208 (descending through the OSI layers 201 through 207) at originating node 21 by sequentially adding service headers 302 through 307. These headers provide information for servicing of the datagram that is interpreted and acted upon by the appropriate functional layer in subsequent nodes through which the datagram is routed, nodes 22, 23, and 24 in the example. At the terminating node 24, the headers are generally stripped away in sequence in ascent through the OSI layers.
Of particular interest here, and as an example of layer communications, the "Network Protocol Data Unit" ("NPDU") 35 (FIGS. 2 and 3) includes protocol control information in the Network Service Header 305 (FIG. 3). Referring to FIG. 2, when NPDU 35 reaches the network layer of router 221 in node 21, the Network Service Header is interpreted by the network layer processor and forwarded according to its routing program on a circuit to the next node, node 23 in this example. Router 221 may alter the service header to include different protocol control information for use by router 23, resulting in a modified NPDU 35' at the Network Layer. Router 23 in turn may generate a modified NPDU 35'' to be serviced by router 241 at the Network Layer, which in the example terminates the transmission of the datagram since node 24, containing router 241, is the end user node. Thus, at the Network Layer 205, what is communicated is the NPDU, and, because of the focus on routing rather than physical connections in network analysis, "data packet" is often treated as synonymous with "NPDU."
While many networks are operated under a single administration, it is common today to have networks owned or operated by different administrations connected to form larger networks. Within such a multi-administration network, the subset of nodes and circuits belonging to a particular administration is here called a "domain." Such a domain is here assumed to be topologically "continuous" in connection space in that every node that is a member of the domain may be connected to every other node in the domain using only nodes and circuits entirely within the domain. In FIG. 1, such a domain 10 is enclosed within domain boundary 110. Again, nodes 13 and 14 may be in the same building, but in different domains (node 13 being "external" to domain 10 and node 14 being "internal"), while nodes 14 and 15, both internal to domain 10 may be separated by many miles.
Although interdomain communication is one of the goals of OSI, there are occasions in which there is a need to prevent the mere "transit" (e.g., data path 100 in FIG. 1) through a domain of data packets which neither originate within nor are addressed to a node within that domain. Without controls, it is possible for "traffic" or data (e.g., originating at external node II) to enter a given "local" domain (e.g., domain 10) at one point (e.g., node 14) and pass through the domain on its way to an external destination (e.g., node 19), making use of the resources of the local domain, such as routers (e.g., routers at nodes 14 through 18), communications channels (e.g., in circuits 142, 151, etc.), and the like.
Such transit merely uses the resources of the local domain without "substantively" communicating with the domain. In the terminology of the OSI Reference Model, such transit uses the lower or network layer communications resources of the domain without communications at the higher or user layers. It may result in denial of resources to traffic involving user communications between local nodes. It may also result in tariffs charged to the local domain administration in those cases where the local domain uses public network links, e.g., telephone company circuits, with tariffs proportional to the traffic carried. It may also make the domain a "common carrier" in violation of local laws.
Thus, it is the goal of the invention to permit communication through a domain only where one or both of the parties to the communication is a member of the domain, while preventing communication through the domain where neither party is a member of the domain.
A "visa scheme" of access control protocol for implementation within OSI has been suggested by D. Estrin, "Interconnection Protocols for Interorganization Networks," IEEE Journal on Selected Areas in Communications, Vol. SAC-5, No. 9, December 1987. In that scheme, depicted in FIG. 1A, at each point or "gateway" of entry into or exit from a domain 120 (gateways 102 and 107, respectively), a data packet or NPDU seeking entry or exit will be rejected unless it carries a valid "visa" authorizing such entry or exit. The visa is initially obtained from an access control server 106 on the basis of the identity of the source and destination of the NPDU.
The Estrin visa scheme can be used to implement a blanket prevention of transit by preventing entry into the domain of any NPDU which does not have a destination within the domain. However, that scheme, in its fully implemented form with time limits on visas, relies upon relatively frequent updates of visa information at the gateways, thus calling for operation considerably more complex than required by the present invention.
Even if it were only selectively implemented and tailored to transit prevention, the Estrin visa approach suffers from the same disadvantage as other approaches of rejecting transit traffic at the point of entry into the local domain. The disadvantage is the requirement of knowledge, at each point of entry, of which destinations are members of the local domain. Such knowledge would require the maintenance of a complete list of domain members at each point of entry (by updating from the access control server) or provision of distributed access to a common list, plus comparison of the destinations of entering data packets with the list. This resource drain would be exacerbated in the context of existing domains which contain hundreds and even thousands of nodes, with commensurate numbers of intended entry points and with additional potential entry points at the connections to common carriers.
Knowledge of the domain membership status of the destination of incoming data packets might also be provided in the destination node addresses by assignment of codes to member nodes indicating their domain membership. For example, the same prefix may be given to the node addresses for each node that is a member of the domain, so that only traffic destined for node addresses with that prefix are allowed to enter the domain. However, given the large number of nodes now typical of many domains, the multiple addresses carried by many nodes, and the frequent subdivisions and additions to such domains, the address code approach is not believed to be manageable because it would require reservation of such codes for present and future domains, the number and size of which are not predictable. There may be other constraints on node addresses that would interfere with such a scheme.